package com.动态规划;

/**
 * 给定一排n个硬币，其值均为正整数c1,c2,c3....cn,这些整数并不一定相同，请问如何选择硬币，使得硬币的原始位置
 * 互不相邻的条件下，所选的硬币总金额最大
 */
public class 币值最大化问题 {

    public static void main(String[] args) {

    }


    /**
     * 使用动态规划 使用一纬数组 存储几个硬币的最大值
     * dp[0] = 0 表示 0个硬币的最大值为0
     * dp[1] = nums[0] 表示 1个硬币的最大值为第一个硬币的值
     * dp[2] = max()
     * <p>
     * 1，8，3，6，5
     * <p>
     * f(1)=1;
     * f(2)=8
     * f(3)=max(8,1)+3;
     * f(4)=max(8,3)
     * <p>
     * 求出选中3时，硬币最大值总和为
     * sum3=max(nums[3]+nums[1],nums[2])
     * sum4=max(nums[4]+nums[2],nums[3]+nums[1])
     * sum5=max(max([],2),max(3,2))
     * <p>
     * <p>
     * 因此规律得出
     * <p>
     * f(5)=
     *
     * @param nums
     * @return
     */
    public int maxNum(int nums[]) {
        int[] dp = new int[nums.length + 1];
        ;
        // 初始值
        dp[0] = 0;
        dp[1] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            dp[i + 1] = Math.max(dp[i + 1 - 2] + nums[i], dp[i]);
        }

        return dp[nums.length + 1];
    }


}
